// 13. [2018统考真题]给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高
// 效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2, 3}中未出现的最小正
// 整数是1;数组{1,2, 3}中未出现的最小正整数是4。要求:
// 1)给出算法的基本设计思想。
// 2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
// 3)说明你所设计算法的时间复杂度和空间复杂度。

// 设一个包含1-n所有数的长度n的序列，
// 把序列中一些值换掉，就变成了题目条件的序列，
// 被换掉的那些位次，就是可能为最小未出现整数

#pragma once
#include "vector"
#include "iostream"
template <typename ElemType>
void printVec(std::vector<ElemType> &vec)
{
    for (auto &i : vec)
    {
        std::cout << i << ",";
    }
    std::cout << "\r\n";
}
template <typename ElemType>
bool findMinPositiveInt(ElemType &retrun_find, std::vector<ElemType> &vec)
{
    int a = 1;
    char *tag = (char *)malloc(vec.size());
    memset(tag, 0, vec.size());
    // ElemType mpv=-1;
    // bool firstFound = false;
    for (int i = 0; i < vec.size(); i++)
    {
        if (vec[i] > 0 && vec[i] <= vec.size())
        {
            //存入时减1
            tag[vec[i] - 1] = 1;
        }
    }
    int i = 0;
    for (; i < vec.size(); i++)
    {
        if (!tag[i])
        {
            retrun_find = i + 1;
            return true;
        }
    }
    retrun_find = i + 1;
    return true;
    // return false;
}
int main()
{
    std::cout << "hello \r\n";
    int arrA[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    int arrB[] = {5, 6, 7, 8};
    // std::vector<int> A =
    //     std::vector<int> B =
    std::vector<int> A(arrA, arrA + sizeof(arrA) / sizeof(int));
    std::vector<int> B(arrB, arrB + sizeof(arrB) / sizeof(int));

    printVec(A);
    printVec(B);
    int find;
    if (findMinPositiveInt(find, A))
    {
        std::cout << "min is \r\n";
        std::cout << find //;
                  << "\r\n";
    }
    else
    {
        std::cout << "not find \r\n";
        // std::cout << findMiddleOfAB(B, A) //;
        //   << "\r\n";
    }

    // std::vector<int> vec1; // vec2, vec3;
    // int arr[100];
    // std::cout << "hello"
    //           << "\r\n";
    // //init data
    // for (int i = 0; i < 100; i++)
    // {
    //     arr[i] = i;
    // }
    // leftMoveArr(arr, 100, 30);

    // // fastFind(vec1, 9);
    // for (int i = 0; i < 100; i++)
    // {
    //     std::cout << arr[i] << ",";
    // }
    // std::cout << "\r\n";
    // for (int i = 0; i < vec2.size(); i++)
    // {
    //     std::cout << vec2[i] << ",";
    // }
    // std::cout << "\r\n";
    // ///////////////////////////////////////////////////
    // combineAB2C(vec1, vec2, vec3);
    // for (int i = 0; i < vec3.size(); i++)
    // {
    //     std::cout << vec3[i] << ",";
    // }
    // std::cout << "\r\n";
    return 0;
}